"""
11月12日达观数据3道在线算法题
"""

def count_zhishu(m, n):
    """第1题，输入m,n(1 < m < n < 1000000)，返回闭区间[m,n]内所有质数的个数"""

    # 本题无法进行算法调优，只能进行两层遍历，时间复杂度O(n^2)
    # 验证输入区间
    if 1 < m < n < 1000000:
        pass
    else:
        return '参数不符合要求：1 < m < n < 1000000'

    # 对区间内的数进行循环，一旦[2, i-1]有一个数能整除i，合数计数器自加
    heshu_count = 0
    for i in range(m, n+1):
        for j in range(2, i):
            # 如果有一个数能被整除，就说明不是质数
            if i % j == 0:
                heshu_count += 1
                break

    # 计算质数
    count = n - m + 1 - heshu_count
    return count


def lengthOfLongestSubstring(s):
    """第2题，求最大不重复子字符串的长度"""

    # 最简单的做法是寻找以每一个字符为开始的最大序列，需要两层遍历，时间复杂度为O(n^2)
    # 高级一点的做法是使用下标字典，一次循环就可以，时间复杂度O(n)

    # 定义历史最大长度
    max_len = 0

    # 定义当前最大长度
    now_max = 0

    # 定义下标字典
    cha_index_dict = {}

    # 定义起始指针
    start = 0

    for i in range(len(s)):
        cha = s[i]

        # 如果上一个字母出现的位置大于等于起始指针，那么更新指针
        # 等于的情况只有在为第一个字母更新指针时才会发生
        if s[i] in cha_index_dict and cha_index_dict[cha] >= start:
            start = cha_index_dict[cha] + 1

        # 记录当前字母的位置，为了下次重复时使用
        cha_index_dict[cha] = i

        now_max = i - start + 1
        max_len = max(now_max, max_len)

    return max_len


def merge2Lists(l1, l2):
    """
    第3题，合并两个有序列表非递归法
    列表数据结构如下：
    class ListNode(object):
        def __init__(self, x):
            self.val = x
            self.next = None
    """

    # 对比两个单链表第一个节点的值，哪个小就取哪个，时间复杂度是O(n)
    # 记录起始节点
    init_listnode = ListNode(20191112)

    # 定义前行节点
    walking = init_listnode

    # 如果两个链表都不为空，对比第一个节点
    while l1 and l2:
        if l1.val < l2.val:
            walking.next = l1
            l1 = l1.next
        else:
            walking.next = l2
            l2 = l2.next
        walking = walking.next

    # 取空一个链表后，就把另一个链表对接进去
    if l1:
        walking.next = l1
    else:
        walking.next = l2

    return init_listnode.next


def merge2Lists_digui(l1, l2):
    """合并两个单链表递归算法"""

    # 思路和算法都是一样的，但是递归确实可以节省很多代码
    if not l1:
        return l2

    if not l2:
        return l1

    if l1.val < l2.val:
        ret_ln = l1
        return merge2Lists_digui(l1.next, l2)
    else:
        ret_ln = l2
        return merge2Lists_digui(l1, l2.next)


if __name__ == '__main__':
    count = count_zhishu(50, 2000)
    print('-'*10 + '第1题' + '-'*10)
    print(count)

    length = lengthOfLongestSubstring('abcebadafgjid')
    print('-'*10 + '第2题' + '-'*10)
    print(length)
